package binaryTree;

import org.junit.Test;

/*
 *@description 从前序与中序遍历序列构造二叉树
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_105 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test(){
        buildTree(new int[]{3,9,20,15,17},new int[]{9,3,15,20,17});
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return solution(preorder,inorder,0,preorder.length-1,0,preorder.length-1);
    }

    private TreeNode solution(int[] preorder, int[] inorder, int startA, int endA, int startB, int endB) {
        if (startA<=endA && startB<=endB){
            TreeNode root = new TreeNode(preorder[startA]);
            int i = find(root.val,inorder);
            root.left=solution(preorder,inorder,startA+1,startA+i-startB,startB,i-1);
            root.right=solution(preorder,inorder,startA+i-startB+1,endA,i+1,endB);
            return root;
        }else {
            return null;
        }
    }

    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (val==inorder[i]){
                return i;
            }
        }
        return -1;
    }

}
